package cz.cvut.fit.mi_paa.knapsack.strategy;

import cz.cvut.fit.mi_paa.abs.Context;
import cz.cvut.fit.mi_paa.knapsack.KnapsackContext;
import cz.cvut.fit.mi_paa.knapsack.Item;

import java.io.FileWriter;
import java.io.IOException;
import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;

/**
 * Created with IntelliJ IDEA.
 * User: milos
 * Date: 2.11.12
 * Time: 7:19
 * To change this template use File | Settings | File Templates.
 */
public class BranchAndBoundKnapsackStrategy extends KnapsackStrategy {
    private Item[] items;
    private int maxWeight;
    private Queue<State> q;
    private State best;
    public BranchAndBoundKnapsackStrategy(Context context) {
        super(context);
        this.items = instance.getItems();
        this.q = new LinkedList<State>();
        this.maxWeight = instance.getCapacity();
        this.best = new State(-1,0,0,new boolean[items.length]);
    }

    @Override
    public void solve() throws IOException {
        int n = items.length;
        int[] remainingVals = new int[n];
        context.getSw().start();
        Arrays.sort(items,new Comparator<Item>() {
            @Override
            public int compare(Item o1, Item o2) {
                return Integer.compare(o2.getPrice(), o1.getPrice());
            }
        });

        for (int i=0; i<n ;i++) {
            for(int j=i; j<n;j++) {
                remainingVals[i] += items[j].getPrice();
            }
        }

        q.offer(new State(-1,0,0,new boolean[n]));
        while (!q.isEmpty()) {
            State s = q.remove();
            if (s.getPrice()>best.getPrice()) best = s;
            for(int i=s.getOrder()+1;i<n;i++) {
                if(s.getWeight()+items[i].getWeight() <= maxWeight) {
                    if(s.getPrice()+remainingVals[i] > best.getPrice()) {
//                        boolean[] used = new boolean[n];
//                        System.arraycopy(s.used, 0, used, 0, s.getOrder()+1);
//                        used[i] = true;
                        q.offer(new State(i,s.getWeight()+items[i].getWeight(),s.getPrice()+items[i].getPrice())) ;
                    }
                }
            }
        }
        context.getSw().stop();
    }

    @Override
    public void writeResult() throws IOException {
        FileWriter resultWriter = context.getResultWriter();
        resultWriter.write(instance.getId() + " ");
        resultWriter.write(context.getSw().getTimeMillis() + " ");
        resultWriter.write(instance.getItemNumber() + " ");
        resultWriter.write(best.getPrice()+ "\n");

//        for (int i = 1; i<best.used.length;i++) {
//            if(i!=(best.used.length-1))
//                resultWriter.write(best.used[i]+" ");
//            else
//                resultWriter.write(best.used[i]+"\n");
//        }
    }

    class State {
        private int order;
        private int weight;
        private int price;
        private boolean[] used;

        State(int order, int weight, int price,boolean[] used) {
            this.order = order;
            this.weight = weight;
            this.price = price;
            this.used = used;
        }

        State(int order, int weight, int price) {
            this.order = order;
            this.weight = weight;
            this.price = price;
        }

        public int getOrder() {
            return order;
        }

        public void setOrder(int order) {
            this.order = order;
        }

        public int getWeight() {
            return weight;
        }

        public void setWeight(int weight) {
            this.weight = weight;
        }

        public int getPrice() {
            return price;
        }

        @Override
        public String toString() {
            return "State{" +
                    "order=" + order +
                    ", weight=" + weight +
                    ", price=" + price +
                    ", used=" + used +
                    '}';
        }

        public void setPrice(int price) {
            this.price = price;
        }
    }
}
